HDU_5813

思路

Elegant Construction
将顶点按能到达的点数从小到大排序，排好序之后每个点只能往前面的点连边. 因而如果存在一个排在第i位的点，要求到达的点数大于i-1，则不可行；否则就可以按照上述方法构造出图. 复杂度O(N^2).

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
#define NV 1000050
int cnt=0;
struct mytl
{
    int a,b;
    bool operator < (const mytl & p)const{
        return b<p.b;
    }
}a[1005],ans[NV];
int main(){
    int t,ca=1;
    scanf("%d",&t);
    for(;ca<=t ;ca++){
        bool has=1;cnt=0;
        int n;scanf("%d",&n);
        for(int i=1 ;i<= n ;i++){
            scanf("%d",&a[i].b);
            a[i].a=i;
        }
        sort(a+1,a+n+1);
        printf("Case #%d: ",ca);
        for(int i=1  ; i<= n ;i++){
            if(a[i].b<=i-1){
                for(int j=1 ; j<=a[i].b ; j++){
                    ans[cnt].a=a[i].a;
                    ans[cnt++].b=a[j].a;
                }
            }
            else{
                has=0;break;
            }
        }
        if(has){
            puts("Yes");
            printf("%d\n",cnt);
            for(int i=0 ; i<cnt ; i++)
            {
                printf("%d %d\n",ans[i].a,ans[i].b);
            }
        }
        else 
            printf("No\n");
    }
    return 0;
}